#pragma once
#include <vector>
#include <stdexcept>
#include <functional>
#include <iostream>

template<typename T, typename Compare = std::less<T>>
class Heap {
public:
    // 类型别名
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using size_type = size_t;

    // 默认构造函数
    Heap() = default;

    // 从初始化列表构造
    Heap(std::initializer_list<T> init) : data_(init) {
        heapify();
    }

    // 析构函数
    ~Heap() = default;

    // 拷贝构造函数
    Heap(const Heap& other) = default;

    // 移动构造函数
    Heap(Heap&& other) noexcept = default;

    // 拷贝赋值运算符
    Heap& operator=(const Heap& other) = default;

    // 移动赋值运算符
    Heap& operator=(Heap&& other) noexcept = default;

    // 交换两个堆
    void swap(Heap& other) noexcept {
        data_.swap(other.data_);
    }

    // 检查堆是否为空
    bool empty() const noexcept {
        return data_.empty();
    }

    // 返回堆的大小
    size_type size() const noexcept {
        return data_.size();
    }

    // 插入元素
    void push(const T& value) {
        data_.push_back(value);
        siftUp(data_.size() - 1);
    }

    // 插入元素（移动语义）
    void push(T&& value) {
        data_.push_back(std::move(value));
        siftUp(data_.size() - 1);
    }

    // 删除堆顶元素
    void pop() {
        if (empty()) {
            throw std::out_of_range("Heap is empty");
        }
        std::swap(data_.front(), data_.back());
        data_.pop_back();
        if (!empty()) {
            siftDown(0);
        }
    }

    // 访问堆顶元素
    const_reference top() const {
        if (empty()) {
            throw std::out_of_range("Heap is empty");
        }
        return data_.front();
    }

    // 清空堆
    void clear() noexcept {
        data_.clear();
    }

    // 打印堆元素
    void print(std::ostream& os = std::cout) const {
        for (const auto& value : data_) {
            os << value << " ";
        }
        os << "\n";
    }

private:
    std::vector<T> data_;
    Compare compare_;

    // 上浮操作
    void siftUp(size_type index) {
        while (index > 0) {
            size_type parent = (index - 1) / 2;
            if (!compare_(data_[index], data_[parent])) {
                break;
            }
            std::swap(data_[index], data_[parent]);
            index = parent;
        }
    }

    // 下沉操作
    void siftDown(size_type index) {
        size_type size = data_.size();
        while (true) {
            size_type leftChild = 2 * index + 1;
            size_type rightChild = 2 * index + 2;
            size_type smallest = index;

            if (leftChild < size && compare_(data_[leftChild], data_[smallest])) {
                smallest = leftChild;
            }

            if (rightChild < size && compare_(data_[rightChild], data_[smallest])) {
                smallest = rightChild;
            }

            if (smallest == index) {
                break;
            }

            std::swap(data_[index], data_[smallest]);
            index = smallest;
        }
    }

    // 建堆操作
    void heapify() {
        for (int i = (data_.size() / 2) - 1; i >= 0; --i) {
            siftDown(i);
        }
    }
};    